P3648 [APIO2014]序列分割

dp[t][i]=max{dp[t1][j]+sj(sisj)}dp[t][i]=\max\{dp[t-1][j] + s_j(s_i-s_j)\}

dp[t][i]=max{dp[t1][j]+sjsisj2}dp[t][i]=\max\{dp[t-1][j] + s_js_i-s_j^2\}

阅读全文 »

P5504 [JSOI2011]柠檬

可以看出,选出区间的端点大小必须相同,不然可以将一端分在其他区间里,答案不会更劣。

dpidp_i 表示前 ii 个贝壳能得到的最大柠檬数, posipos_i 表示第 ii 个贝壳是第几个这种颜色的贝壳。

那么有转移:

阅读全文 »

P4072 [SDOI2016]征途

dp[i][j]=min(dp[i1][k]+(SumjSumk)2)   (0k<j)dp[i][j]=min(dp[i-1][k]+(Sum_j-Sum_k)^2) ~~~ (0 \le k < j)

dp[i][j]=min(dp[i1][k]+Sumj2+Sumk22SumiSumk)   (0k<j)dp[i][j]=min(dp[i-1][k]+Sum_j^2+Sum_k^2-2Sum_iSum_k) ~~~ (0 \le k < j)

阅读全文 »

P2365 & P5785 任务安排

两道题的转移式是一样的,只是优化不同。

dp(i)dp(i) 为完成前 ii 个任务的最小花费。

你会发现每次操作后总时间会增加 ss ,这样就不好处理当前时间。

阅读全文 »

CF906C Party

首先预处理出一个人能介绍的人的集合 relrel 。(包括他本身)

dp(S)dp(S) 表示让集合 SS 中的人相互认识最少需要几个人。

那么可以刷表转移:

阅读全文 »

UVA1407 Caves

一道标准的树形dp。

dp[u][i][0/1]dp[u][i][0/1] 表示以 uu 为根的子树 , 探索 ii 个洞穴,是否回到 uu

显然有:

阅读全文 »

CF815C Karen and Supermarket

因为使用优惠劵就必须买这件商品,我们可以将优惠劵的关系看成一棵树。

dp[u][i][0/1]dp[u][i][0/1] 表示 以 uu 为根的子树 , 购买 ii 件商品 , uu 是否使用优惠劵的最小花费。

边界条件:dp[u][0][0]=0,dp[u][1][0]=c[u],dp[u][1][1]=c[u]d[u]dp[u][0][0]=0,dp[u][1][0]=c[u],dp[u][1][1]=c[u]-d[u]

阅读全文 »

P5176 公约数

首先有一个结论:

gcd(ij,ik,jk)=gcd(i,j)gcd(j,k)gcd(i,k)gcd(i,j,k)gcd(i\cdot j,i\cdot k,j\cdot k)=\frac{gcd(i , j )\cdot gcd(j , k) \cdot gcd(i,k)}{gcd(i,j,k)}

阅读全文 »